<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<title>/media/src/Dropbox/TC/SingleRoundMatch/SRM165/SRM165DIV2_1150.java.html</title>
<meta name="Generator" content="Vim/7.2">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
</head>
<body bgcolor="#ffffff" text="#000000"><font face="monospace">
<font color="#8080ff">//Mon Oct&nbsp;&nbsp;3 00:08:09 PDT 2011</font><br>
<font color="#ff40ff">import</font>&nbsp;java.util.*;<br>
<font color="#ff40ff">import</font>&nbsp;java.util.regex.*;<br>
<font color="#ff40ff">import</font>&nbsp;java.text.*;<br>
<font color="#ff40ff">import</font>&nbsp;java.math.*;<br>
<font color="#ff40ff">import</font>&nbsp;java.awt.geom.*;<br>
<br>
<font color="#00ff00">public</font>&nbsp;<font color="#00ff00">class</font>&nbsp;ShortPalindromes {<br>
<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">public</font>&nbsp;String[][]&nbsp;dp;<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">public</font>&nbsp;String str;<br>
<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">public</font>&nbsp;String shortest(String base)&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;str = base;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dp = <font color="#ffff00">new</font>&nbsp;String[str.length()&nbsp;+ <font color="#ff6060">1</font>][str.length()&nbsp;+ <font color="#ff6060">1</font>];<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">return</font>&nbsp;solve(<font color="#ff6060">0</font>, str.length());<br>
&nbsp;&nbsp;&nbsp;&nbsp;}<br>
<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">public</font>&nbsp;String solve(<font color="#00ff00">int</font>&nbsp;left, <font color="#00ff00">int</font>&nbsp;right)&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">if</font>&nbsp;(left + <font color="#ff6060">1</font>&nbsp;&gt;= right)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">return</font>&nbsp;str.substring(left, right);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">if</font>&nbsp;(dp[left][right]&nbsp;!= <font color="#ff6060">null</font>)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">return</font>&nbsp;dp[left][right];<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">if</font>&nbsp;(str.charAt(left)&nbsp;== str.charAt(right - <font color="#ff6060">1</font>))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">return</font>&nbsp;dp[left][right]&nbsp;= str.charAt(left)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;+ solve(left + <font color="#ff6060">1</font>, right - <font color="#ff6060">1</font>)&nbsp;+ str.charAt(left);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;String s1 = str.charAt(left)&nbsp;+ solve(left + <font color="#ff6060">1</font>, right)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;+ str.charAt(left);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;String s2 = str.charAt(right - <font color="#ff6060">1</font>)&nbsp;+ solve(left, right - <font color="#ff6060">1</font>)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;+ str.charAt(right - <font color="#ff6060">1</font>);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">if</font>&nbsp;(s1.length()&nbsp;&lt; s2.length())<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">return</font>&nbsp;dp[left][right]&nbsp;= s1;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">else</font>&nbsp;<font color="#ffff00">if</font>&nbsp;(s1.length()&nbsp;&gt; s2.length())<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">return</font>&nbsp;dp[left][right]&nbsp;= s2;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">else</font>&nbsp;<font color="#ffff00">if</font>&nbsp;(s1.compareTo(s2)&nbsp;&lt; <font color="#ff6060">0</font>)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">return</font>&nbsp;dp[left][right]&nbsp;= s1;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">else</font><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">return</font>&nbsp;dp[left][right]&nbsp;= s2;<br>
&nbsp;&nbsp;&nbsp;&nbsp;}<br>
<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#8080ff">// &lt;%:testing-code%&gt;</font><br>
}<br>
<font color="#8080ff">// Powered by [KawigiEdit] 2.0!</font><br>
</font></body>
</html>
